package star.基础.堆排序;

import star.Utils;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5,3,6,7,8,9,5};
        heapSort(arr);
        Utils.traversal(arr);
    }

    private static void heapSort(int[] arr){
        if (arr.length < 2 || arr == null) return;
        int heapSize = arr.length;
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr,i);
        }
        Utils.swap(arr,0,--heapSize);
        while (heapSize>0){
            heapify(arr,0,heapSize);
            Utils.swap(arr,0,--heapSize);
        }
    }
    private static void heapify(int[] arr,int index,int heapSize){
        int left = 2 * index + 1;
        while (left < heapSize){
            int large = left+1 < heapSize && arr[left+1] > arr[left] ? left+1 :left;
            large = arr[large] > arr[index] ? large : index;
            if (large == index) break;
            Utils.swap(arr,large,index);
            index = large;
            left = 2 * index + 1;
        }
    }

    private static void heapInsert(int[] arr,int index){
        while (arr[index] > arr[(index-1)/2]){
            Utils.swap(arr,index,(index-1)/2);
            index = (index-1)/2;
        }
    }
}
